package com.banyuan.HomeWork.集合类.数据结构;

import javax.swing.tree.AbstractLayoutCache;

public class MyLinkedList {
    private Node first;
    private int size;

    //添加一个元素到头部；
    public void addFirst(Object obj) {
//        if(size == 0){
//            first = new Node(obj);
//        }else{
//            first = new Node(obj,first);
//        }
//        size++;

        first = new Node(obj, first);
        size++;
    }

    //删除头部的元素
    public void removeFirst() {
        //判断Linked是否为空；
        if (first == null) {
            throw new NullPointerException();
        } else {
            first = first.getNext();
            size--;
        }
    }

    //按下标寻找元素；
    public Object get(int index) {
//        //index越界的错误；
//        if (index < 0||index >=size){
//            throw new IndexOutOfBoundsException();
//        }
//        Node temp = first;
//        //这个循环最好验证一下，first为null的情况；
//        for (int i = 0; i < index; i++) {
//            temp = temp.getNext();
//        }

        return getNode(index).getObj();
    }

    //将一个元素添加到LinkedList的尾部；
    public void addLast(Object obj) {

        //这样写也行，但是判断的次数会有点多；可以直接判断next是否为null，来确定是不是尾部节点；
        //注意这个要判断LinkedList是否为空
//        if（first == null）{
//            addFirst(obj);
//        }else{
//            Node temp = first;
//            for (int i = 0; i < size - 1; i++) {
//                temp = temp.getNext();
//            }
//            temp.setNext(new Node(obj));
//        }
//        size++;


        if (first == null) {
            addFirst(obj);
        } else {
            Node temp = first;
            Node node = new Node();
            node.setObj(obj);
            while (temp.getNext() != null) {
                temp = temp.getNext();
            }
            temp.setNext(node);
        }
        size++;
    }

    //删除尾部的元素；
    public void removeLast() {
        //第一个if判断LinkedList为空的时候抛出一个空指针异常；
        //第二个if判断尾节点就是首节点的情况；
        if (first == null) {
            throw new NullPointerException();
        } else if (first.getNext() == null) {
            first = null;
        } else {
            Node temp = new Node();
            while (temp.getNext().getNext() != null) {
                temp = temp.getNext();
            }
        }
        size--;
    }

    //添加一个元素到LinkedList的指定下标位；
    public void add(int index, Object o) {

        //首先要做一个index越界的判断；
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        //建立前后节点的关系；
        //判断LinkedList是否为空，为空的话就增加首节点，同时普安段当index为0的时候就是首节点，调用首节点的方法；
        //为了避免出现空指针的情况，需要将判断为空的情况放在签满；
        if (first == null || index == 0) {
            addFirst(o);
        } else {
            //创建一个新的节点；
            Node node = new Node();
            //将需要存储的内容放入存储区；
            node.setObj(o);
            //找到这个节点的前一个节点，由于前一个节点保存的是当前index的地址，所以不能先覆盖，要将这个地址值先传给node的next；
            node.setNext(getNode(index - 1).getNext());
            //将node的地址值传入到index-1的节点的next中；
            getNode(index - 1).setNext(node);

        }
        size++;
    }

    //删除LinkedList给定的下标处的元素；
    //同样需要判断是否为空的情况；
    public void remove(int index) {

        /*
         * 考虑几种情况
         * 1、LinkedList为空的情况；
         * 2、index越界的情况；
         * 3、只有一个元素的情况；
         * 4、当index为0的情况；//可以调用remove方法，这个也解决了第三种的情况；
         * */
        if (first == null) {
            throw new NullPointerException();
        } else if (index <0 || index >=size) {
            throw new IndexOutOfBoundsException();
        } else if (index == 0) {
            removeFirst();
        } else {
           getNode(index - 1).setNext(getNode(index).getNext());
        }
    }

    //创建一个私有的getNode方法，方便add和get的调用；
    private Node getNode(int index) {
        //注意验证LinkedList为空的情况；
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node temp = first;
        for (int i = 0; i < index; i++) {
            temp = temp.getNext();
        }
        return temp;

    }

    @Override
    public String toString() {
        String s = "";
        Node temp = first;
        if (first == null) {
            System.out.println("null");
        } else {
            s += temp.toString();
            while (temp.getNext() != null) {
                temp = temp.getNext();
                s += " " + temp.toString();
            }
        }
        return "{" + s + "}";
    }
}


//一个内部类；
//LinkedList的节点，组成LinkedList的单元，内部的信息有需要保存的数据的引用，以及下一个节点的地址；
class Node {
    //字段用于保存数据；
    private Object obj;

    @Override
    public String toString() {
        return obj.toString();
    }

    //保存下一个节点的地址；
    private Node next;

    public Node() {
    }

    public Node(Object obj) {
        this.obj = obj;
    }

    public Node(Object obj, Node next) {
        this.obj = obj;
        this.next = next;
    }

    public Object getObj() {
        return obj;
    }

    public void setObj(Object obj) {
        this.obj = obj;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}
